Three-dimensional graphics processing is utilized in a number of applications, from electronic games, and movies to computer aided design (CAD). Conventionally, three-dimensional graphics processing includes a multi-step rendering process of transitioning from a database representation of three-dimensional objects to a pseudo realistic two-dimensional projection of the object into a display space. The process generally includes setting up a polygon model (e.g., a plurality of primitives) of objects, applying linear transformation to each primitive, culling back facing primitives, clipping the primitives against a view volume, rasterizing the primitives to a pixel coordinate set, applying textures to the primitives, shading/lighting the individual pixels, and the like.
The textures, utilized in graphics processing, may be stored as mipmaps in memory. Referring to FIG. 1, an exemplary mipmap, in accordance with the conventional art, is shown. As depicted in FIG. 1, a mipmap contains a plurality of miplevels 110-170. The base miplevel 110 contains the highest resolution version of a given texture (e.g., finest resolution). The resolution of the texture successively decreases in each next higher miplevel. Each texel of a given miplevel typically corresponds to the average of the corresponding four texels in the previous miplevel (e.g., next lower miplevel). Thus, each successive miplevel 130 has a resolution that is one-quarter of the previous miplevel 120. The highest miplevel 170 (e.g. coarsest miplevel) typically is a single texel value corresponding to the average of all the texels in the base miplevel 110. The appropriate miplevel to be applied to a primitive is typically determined by a level of detail (LOD). The LOD of the base miplevel is zero, and the highest LOD identifies the coarsest miplevel.
Referring now to FIG. 2, an exemplary primitive and an exemplary texture to be applied to the primitive, in accordance with the conventional art, is shown. As depicted in FIG. 2, the primitive 210 (e.g., triangle) is rasterized thereby generating a plurality of pixels 230. The exemplary texture 220 may be an appropriate miplevel in a mipmap as determined by the level of detail of the primitive. The primitive 210, in view space, is projected onto the texture 220, in plane space. One or more texels 240 in the texture are thereby associated with each corresponding pixel 230.
A grid pattern has been superimposed upon the texture 220 to illustrate how the texture 220 is stored in memory, in accordance with the conventional art. Each square of the grid represents a texel 240. The texels typically occupy one or more bytes of memory. It is appreciated that a page of memory may be defined as a consecutive range of addresses, typically a power of two in size. There is generally a non-zero cost when a memory read or write operation has to switch from one page to another. In an exemplary implementation, assuming each texel is 4 bytes in size, the texture is 1024×1024 texels in size, the page is 4096 bytes, and the texture starts at the beginning of a page, then each row of the texture may occupy a page.
For purposes of illustration only, the light vertical gradations represent the four-byte boundaries of each texel 240 and the dark horizontal gradations represent the 16 page boundaries. It is appreciated that memory accesses within a row of the texture map do not incur a page-crossing cost, whereas memory accesses that access different rows do incur a page-crossing cost. Accordingly, the exemplary primitive 210 projected onto the exemplary texture 220, illustrates the memory access costs of conventional art texturing methods. As illustrated, ten page boundaries are crossed when applying the exemplary texture to the exemplary primitive.
Referring now to FIGS. 3A, 3B and 3C, exemplary memory layouts (e.g., logical organizations) for storing texture data, in accordance with the conventional art, are shown. As depicted in FIG. 3A, texel data may be stored in a computer-readable medium in a pitch linear format. In pitch linear format, the texels of a mipmap are stored sequentially in memory. More specifically, texels in a given row are stored sequentially and then the texels in the next row are stored sequentially and so on. For example, an exemplary page partition may be equal to 1024 bytes of memory. An exemplary texel may be equal to 4 bytes. Thus, the first 256 texels in sequence are stored in a page of memory: The memory access costs of pitch linear format is proportional to the total number of page boundaries. For example, the following representation of pitch linear organized texel data assumes that each digit represents a single texel, and the digit value represents the page on which the texel resides (e.g., 8 pages):                00000000        11111111        22222222        33333333        44444444        55555555        66666666        77777777It is appreciated that for ease of understanding, only the first 8 columns and rows of the texture are shown. If 15 lines are drawn through this 8×8 texel portion of the texture, the first line is completely horizontal across 8 texels, the second line slopes all the way across 8 texels and down 1 texel, the third line slopes more steeply all the way across 8 texels and down 2 texels, and so on to the final line which extends 8 texels completely vertically. The first line touches texels on a single page: page 0. The second line touches texels on two pages: pages 0 and 1. The eighth through fifteenth lines touch texels on all eight pages. In summary, each of the 15 lines cross 1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8 pages, respectively. Thus, the page-crossing cost for pitch linear is proportional to 92.        
This layout is fine, if the texels are accessed horizontally across each row. However, typical access patterns have 2D (or 3D for 3D textures) spatial locality. Thus, accesses that are closely spaced in time are likely to proceed to nearby texels in any direction, not just horizontally. The orientation of this spatial locality cannot be predetermined, as it depends upon the observer's point of view. Thus, the same texture will have different patterns of spatial locality as the observer moves around. Accordingly, what is desired is a memory organization that works well regardless of the orientation of the spatial locality.
As depicted in FIG. 3B, texel data may be stored in a computer-readable medium in a block linear format. In block linear format, the memory is logically organized into a plurality of blocks, which are a function of a specific page size of the particular implementation. Texels of a mipmap are stored in xyz block ordering. Within each block the texels are stored sequentially in memory. In an exemplary block linear format, a page of memory contains 8 sequential 4-byte texels (e.g., 32 bytes) in 32 sequential rows. The memory access costs (e.g., latency) of block linear format is proportional to the total number of page boundaries. For example, the following representation of block linear organized texel data assumes that each digit represents a single texel, and the digit value is the page upon which the texel resides (e.g., 4 pages):                00001111        00001111        00001111        00001111        22223333        22223333        22223333        22223333In this example, the 8×8 texels of interest have been offset from the upper left corner of the texture by 4 texels horizontally and vertically. (Else all 64 texels would lie on page 0.) Now the total number of pages crossed by 15 lines are: 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 2, 2, 2. Thus, the page-crossing cost for pitch linear is proportional to 36. It is appreciated that the actual block linear mapping is more complicated. However, the fewer page crossings, of the above examples, illustrate that the block linear page organization is better than the pitch linear page organization.        
As depicted in FIG. 3C, if the mipmap is not a power of two bytes in size, a portion of the memory space is not utilized. For example, a texture may be 140 texels high and 129 texels wide, wherein each texel consumes 4 bytes. As a result, 14,800 bytes of memory are allocated for storing the texture but are not utilized. Thus, conventional block linear formats suffer from un-utilized memory when the textures are not a power of two.